#ifndef _MY_HEAP_H_
#define _MY_HEAP_H_

#include <algorithm>
#include <iostream>
#include <vector>

constexpr bool debug_info = true;

template <typename T> class my_heap
{
  private:
    std::vector<T> heap_vec;
    /* 表示堆的类型，true为大顶堆，false为小顶堆 */
    /* 默认为大顶堆 */
    bool heap_type = true;
    void insert_node_helper(const T &node);
    /* 自顶向下执行堆化 */
    void sift_down(int);
    /* 自底向上执行堆化 */
    void sift_up(int);
    void create_heap_by_vec(const std::vector<T> &vector_list, bool);

  public:
    my_heap() = default;
    my_heap(const std::vector<T> &vector_list) { create_heap_by_vec(vector_list, true); };
    my_heap(const std::vector<T> &vector_list, bool heap_type) { create_heap_by_vec(vector_list, heap_type); };
    ~my_heap() { std::cout << "执行析构\n"; };
    void insert_node(const T &node) { insert_node_helper(node); };
    T pop_top();
    int left(int index) { return (2 * index + 1); };
    int right(int index) { return (2 * index + 2); };
    int parent(int index) { return ((index - 1) / 2); };
    void level_traversal();
};

template <typename T> void my_heap<T>::level_traversal()
{
    std::cout << "层序遍历: ";
    for (auto item : heap_vec) {
        std::cout << item << " ";
    }
    std::cout << std::endl;
}

template <typename T> void my_heap<T>::create_heap_by_vec(const std::vector<T> &vector_list, bool heap_type)
{
    /* 保存堆的类型 */
    this->heap_type = heap_type;
    /* 先将所有节点存到堆里 */
    heap_vec = vector_list;

    auto heap_size = heap_vec.size();
    /* 1. 从最后一个非叶节点(this->parent(heap_size - 1))开始，自底向上执行堆化 */
    /* 2. 对于叶节点，由于其没有子节点，因此其已经满足堆的定义，不必再执行堆化了 */
    /* 此处的i一定要用有符号整数，如果用无符号整数，当0-1的时候，将会得到无符号的最大整数，此处就会有问题 */
    for (int i = this->parent(heap_size - 1); i >= 0; --i) {
        std::cout << "开始对 " << heap_vec[i] << " 执行堆化, i: " << i << "\n";
        sift_down(i);
    }
}

template <typename T> void my_heap<T>::sift_down(int i)
{
    if (heap_vec.empty()) {
        std::cout << "堆为空\n";
        return;
    }

    /* 检查当前节点及其左右子节点，谁的值更大或者更小 */
    int left = 0;
    int right = 0;
    int max_node = 0;
    int min_node = 0;
    int heap_size = heap_vec.size();

    /* 大顶堆 */
    if (this->heap_type == true) {
        while (true) {
            left = this->left(i);
            right = this->right(i);
            max_node = i;

            /* 下面的两个 if 判断，是要找出子节点中，较大的那个节点 */
            if (left < heap_size && heap_vec[left] > heap_vec[max_node]) {
                max_node = left;
            }

            if (right < heap_size && heap_vec[right] > heap_vec[max_node]) {
                max_node = right;
            }

            /* 最大值为当前节点，不需要堆化 */
            if (max_node == i) {
                break;
            }

            /* 交换节点的值 */
            std::swap(heap_vec[max_node], heap_vec[i]);

            /* 将i重置为当前的最大节点 */
            i = max_node;
        }

    } else {
        /* 小顶堆，相关逻辑和上述大顶堆的相反 */
        while (true) {
            left = this->left(i);
            right = this->right(i);
            min_node = i;

            if (left < heap_size && heap_vec[left] < heap_vec[min_node]) {
                min_node = left;
            }

            if (right < heap_size && heap_vec[right] < heap_vec[min_node]) {
                min_node = right;
            }

            /* 最大值为当前节点，不需要堆化 */
            if (min_node == i) {
                break;
            }

            std::swap(heap_vec[min_node], heap_vec[i]);

            i = min_node;
        }
    }
}

template <typename T> void my_heap<T>::sift_up(int i)
{
    if (heap_vec.empty()) {
        std::cout << "堆为空\n";
        return;
    }

    int parent = 0;
    int heap_size = heap_vec.size();

    /* 大顶堆 */
    if (this->heap_type == true) {
        while (true) {
            /* 获取父节点 */
            parent = this->parent(i);
            /* 1. 需要判断父节点是否是正常的节点（可能超出索引） */
            /* 2. 对比当前节点的值和父节点的值，谁更大 */
            if (parent < 0 || heap_vec[parent] >= heap_vec[i]) {
                break;
            }

            /* 满足上面的条件，在此处交换节点的值 */
            std::swap(heap_vec[parent], heap_vec[i]);
            i = parent;
        }
    } else {
        /* 小顶堆 */
        while (true) {
            parent = this->parent(i);
            if (parent < 0 || heap_vec[parent] <= heap_vec[i]) {
                break;
            }

            std::swap(heap_vec[parent], heap_vec[i]);
            i = parent;
        }
    }
}

template <typename T> void my_heap<T>::insert_node_helper(const T &node)
{
    /* 先将节点插入到堆的尾部 */
    heap_vec.push_back(node);
    /* 自底向上执行堆化 */
    sift_up(heap_vec.size() - 1);
}

template <typename T> T my_heap<T>::pop_top()
{
    /* 1. 记录一下堆顶元素 */
    T heap_top = heap_vec[0];

    /* 2. 将堆顶和堆底互换 */
    std::swap(heap_vec[0], heap_vec[heap_vec.size() - 1]);

    /* 3. 将堆顶元素出堆 */
    heap_vec.pop_back();

    /* 4. 自顶向下执行堆化 */
    sift_down(0);

    return heap_top;
}

#endif